Compression methods and algorithms are well known in the art for reducing the amount of data to be stored in memory. In particular, different algorithms are known for different types of data, e.g. JPEG for images.
The present application is directed to the compression of matrix structures.
One approach previously attempted (Moloney & Geraghty WO2006120664) involved compressing matrix structures by converting an unstructured matrix into a structured matrix. The compression method effectively eliminated duplication of data above and below the primary diagonal of the matrix.
Another method for dealing with matrix structures is proposed in U.S. Pat. No. 6,591,019 in which a matrix of data values is compressed into a structure comprising a bitMap table, a signMap table and a dataMap table. The bitmap table comprises a series of 2-bit entries, each 2-bit entry corresponding to an entry in uncompressed matrix structure. Each two bit entry in the bitMap identifies whether the corresponding value in the non-compressed matrix is either a zero or a one or stored in scaled form in the dataMap or stored in uncompressed form in the dataMap. The signMap table identifies the signs of the values in the non-compressed structure. A disadvantage of this method is that it is not lossless as information is lost in scaling values. The method is only practical for implementation in software.
Allthough each of the above methods offers an improvement over the prior art insofar as less memory is required to store the structures in memory, the methods still incur a significant computation cost when decompressing the structures in the processor. Additionally both of the above methods also suffer in terms of processing speed owing to their relative complexity in terms of both compression and decompression, which when run on a processor results in an apparatus which is relatively large and slow in terms of performance.
The present application addresses the problem in the design of computing systems of minimising the cost of memory access while minimising the implementation cost and maximising the compression/decompression speed of the implementation. The cost of memory access (memory bandwidth) is a fundamental limitation on the design of computer systems as regardless of the memory technology or manner of connection to the processor, there is a maximum limitation on how much data can be transferred between processor and memory in a given time, this is the available memory bandwidth and the limitation of compute power by available memory bandwidth is often referred to as the “memory-wall”
The present application seeks to increase the effective memory bandwidth and minimise the limitation of the “memory-wall” on computation by storing data in a compressed format, and providing a means of compression and decompression which is suitable for block-structured data used in many applications such as computer graphics, rigid-body dynamics, finite-element analysis and other scientific and engineering applications, which operate on large data sets which must be stored in memory.